Centrality | Social Network Analysis¶

Dr. Chan, Chun-Hsiang @ Department of Geography,
National Taiwan Normal University, Taipei, Taiwan

Graph initialization¶

In [1]:
# import packages
import numpy as np
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
import random
In [2]:
# network initialization
star = nx.Graph([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6)])
line = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)])
circle = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)])
In [3]:
attr_6 = {0: "A", 1: "B", 2: "C", 3: "D", 4: "E", 5: "F"}
attr_7 = {0: "A", 1: "B", 2: "C", 3: "D", 4: "E", 5: "F", 6: "G"}

star = nx.relabel_nodes(star, attr_7)
line = nx.relabel_nodes(line, attr_6)
circle = nx.relabel_nodes(circle, attr_6)
In [4]:
options = {
    "font_size": 14,
    "node_size": 800,
    "node_color": "#A0CBE2",
    "edge_color": "skyblue",
    "linewidths": 1,
    "width": 2,
}

plt.subplots(figsize=[12,4], dpi=300)
plt.subplot(131)
nx.draw_networkx(star,  **options, with_labels = True)
ax = plt.gca()
ax.margins(0.20)
plt.axis("off")

plt.subplot(132)
nx.draw_networkx(line,  **options, with_labels = True)
ax = plt.gca()
ax.margins(0.20)
plt.axis("off")

plt.subplot(133)
nx.draw_networkx(circle,  **options, with_labels = True)
ax = plt.gca()
ax.margins(0.20)
plt.axis("off")

plt.show()

Centrality Measurement¶

Degree Centrality¶

In [5]:
# degree centrality: star network
nx.algorithms.centrality.degree_centrality(star)
Out[5]:
{'A': 1.0,
 'B': 0.16666666666666666,
 'C': 0.16666666666666666,
 'D': 0.16666666666666666,
 'E': 0.16666666666666666,
 'F': 0.16666666666666666,
 'G': 0.16666666666666666}
In [6]:
# degree centrality: line network
nx.algorithms.centrality.degree_centrality(line)
Out[6]:
{'A': 0.2, 'B': 0.4, 'C': 0.4, 'D': 0.4, 'E': 0.4, 'F': 0.2}
In [7]:
# degree centrality: circle network
nx.algorithms.centrality.degree_centrality(circle)
Out[7]:
{'A': 0.4, 'B': 0.4, 'C': 0.4, 'D': 0.4, 'E': 0.4, 'F': 0.4}
In [8]:
# re-label again
star = nx.relabel_nodes(star, attr_7)
line = nx.relabel_nodes(line, attr_6)
circle = nx.relabel_nodes(circle, attr_6)

Closeness Centrality¶

In [9]:
# closeness centrality: star network
nx.algorithms.centrality.closeness_centrality(star)
Out[9]:
{'A': 1.0,
 'B': 0.5454545454545454,
 'C': 0.5454545454545454,
 'D': 0.5454545454545454,
 'E': 0.5454545454545454,
 'F': 0.5454545454545454,
 'G': 0.5454545454545454}
In [10]:
# closeness centrality: line network
nx.algorithms.centrality.closeness_centrality(line)
Out[10]:
{'A': 0.3333333333333333,
 'B': 0.45454545454545453,
 'C': 0.5555555555555556,
 'D': 0.5555555555555556,
 'E': 0.45454545454545453,
 'F': 0.3333333333333333}
In [11]:
# closeness centrality: circle network
nx.algorithms.centrality.closeness_centrality(circle)
Out[11]:
{'A': 0.5555555555555556,
 'B': 0.5555555555555556,
 'C': 0.5555555555555556,
 'D': 0.5555555555555556,
 'E': 0.5555555555555556,
 'F': 0.5555555555555556}

define a new graph¶

In [12]:
bet = nx.Graph([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (2, 4), 
                (3, 4), (4, 5), (3, 5), (6, 7), (6, 8), (7, 8), (2, 7)])
attr_8 = {0: "A", 1: "B", 2: "C", 3: "D", 4: "E", 5: "F", 6: "G", 7: "H", 8: "I"}
bet = nx.relabel_nodes(bet, attr_8)

options = {
    "font_size": 14,
    "node_size": 800,
    "node_color": "#A0CBE2",
    "edge_color": "skyblue",
    "linewidths": 1,
    "width": 2,
}

plt.subplots(figsize=[6,6], dpi=100)
nx.draw_networkx(bet,  **options, with_labels = True)
ax = plt.gca()
ax.margins(0.20)
plt.axis("off")
plt.show()

Betweenness Centrality¶

In [13]:
# betweenness centrality: star network
nx.algorithms.centrality.betweenness_centrality(star)
Out[13]:
{'A': 1.0, 'B': 0.0, 'C': 0.0, 'D': 0.0, 'E': 0.0, 'F': 0.0, 'G': 0.0}
In [14]:
# betweenness centrality: circle network
nx.algorithms.centrality.betweenness_centrality(circle)
Out[14]:
{'A': 0.2, 'B': 0.2, 'C': 0.2, 'D': 0.2, 'E': 0.2, 'F': 0.2}
In [15]:
# betweenness centrality: bet network
nx.algorithms.centrality.betweenness_centrality(bet)
Out[15]:
{'A': 0.14880952380952378,
 'B': 0.0,
 'C': 0.5654761904761904,
 'D': 0.029761904761904757,
 'E': 0.25595238095238093,
 'F': 0.0,
 'G': 0.0,
 'H': 0.42857142857142855,
 'I': 0.0}

Eigenvector Centrality¶

In [16]:
# get adjacency matrix
A_star = nx.adjacency_matrix(star)
A_star
Out[16]:
<7x7 sparse matrix of type '<class 'numpy.intc'>'
	with 12 stored elements in Compressed Sparse Row format>
In [17]:
# sparse array to dense array
A_star = np.array(A_star.todense())
A_star
Out[17]:
array([[0, 1, 1, 1, 1, 1, 1],
       [1, 0, 0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 0, 0]], dtype=int32)
In [18]:
# compute eigen value and eigen vector
eigval, eigvec = np.linalg.eig(A_star)
print(eigvec[:,0])

[0.70710678 0.28867513 0.28867513 0.28867513 0.28867513 0.28867513
 0.28867513]
In [19]:
# eigenvector centrality: star network
nx.algorithms.centrality.eigenvector_centrality(star)
Out[19]:
{'A': 0.7071065004428642,
 'B': 0.2886752492078963,
 'C': 0.2886752492078963,
 'D': 0.2886752492078963,
 'E': 0.2886752492078963,
 'F': 0.2886752492078963,
 'G': 0.2886752492078963}
In [20]:
# eigenvector centrality: line network
nx.algorithms.centrality.eigenvector_centrality(line)
Out[20]:
{'A': 0.23192160753344954,
 'B': 0.41790694813836154,
 'C': 0.5211200923556694,
 'D': 0.5211200923556694,
 'E': 0.41790694813836154,
 'F': 0.23192160753344954}
In [21]:
# eigenvector centrality: circle network
nx.algorithms.centrality.eigenvector_centrality(circle)
Out[21]:
{'A': 0.408248290463863,
 'B': 0.408248290463863,
 'C': 0.408248290463863,
 'D': 0.408248290463863,
 'E': 0.408248290463863,
 'F': 0.408248290463863}
In [22]:
# eigenvector centrality: bet network
nx.algorithms.centrality.eigenvector_centrality(bet)
Out[22]:
{'A': 0.4852872084486325,
 'B': 0.28399437654374904,
 'C': 0.44032475490042544,
 'D': 0.37698974976988026,
 'E': 0.48037037436471447,
 'F': 0.2630529062807772,
 'G': 0.08209992568621469,
 'H': 0.18548055028104896,
 'I': 0.08209992568621469}

HITS Algorithm¶

In [23]:
# graph initialization
dir_ex = nx.DiGraph([(0, 1), (0, 2), (1, 2), (2, 1), (1, 3), (2, 3), (3, 2), (2, 4)])
attr_5 = {0: "A", 1: "B", 2: "C", 3: "D", 4: "E"}
dir_ex = nx.relabel_nodes(dir_ex, attr_5)

options = {
    "font_size": 14,
    "node_size": 800,
    "node_color": "#A0CBE2",
    "edge_color": "skyblue",
    "linewidths": 1,
    "width": 2,
}

# draw the graph
plt.subplots(figsize=[6,6], dpi=100)
nx.draw_networkx(dir_ex,  **options, with_labels = True)
ax = plt.gca()
ax.margins(0.20)
plt.axis("off")
plt.show()
In [24]:
# run HITS algorithm
hub, auth = nx.hits(dir_ex, max_iter=1)
hub, auth
Out[24]:
({'A': 0.26959443640544456,
  'B': 0.26959443640544456,
  'C': 0.31544880690757227,
  'D': 0.1453623202815386,
  'E': 0.0},
 {'A': 0.0,
  'B': 0.26959443640544456,
  'C': 0.3154488069075723,
  'D': 0.26959443640544456,
  'E': 0.1453623202815386})

Information Centrality¶

In [25]:
# information centraltiy: star network
nx.algorithms.centrality.information_centrality(star)
Out[25]:
{'A': 0.16666666666666666,
 'B': 0.09090909090909091,
 'C': 0.09090909090909091,
 'D': 0.09090909090909091,
 'E': 0.09090909090909091,
 'F': 0.09090909090909091,
 'G': 0.09090909090909091}
In [26]:
# information centraltiy: circle network
nx.algorithms.centrality.information_centrality(circle)
Out[26]:
{'A': 0.17142857142857149,
 'B': 0.17142857142857143,
 'C': 0.17142857142857146,
 'D': 0.17142857142857149,
 'E': 0.17142857142857146,
 'F': 0.17142857142857146}
In [27]:
# information centraltiy: line network
nx.algorithms.centrality.information_centrality(line)
Out[27]:
{'A': 0.0666666666666667,
 'B': 0.09090909090909094,
 'C': 0.1111111111111111,
 'D': 0.11111111111111116,
 'E': 0.09090909090909093,
 'F': 0.0666666666666667}

Pagerank¶

In [28]:
# pagerank
nx.pagerank(dir_ex, alpha=0.9)
Out[28]:
{'A': 0.04870802791836645,
 'B': 0.1814084107966842,
 'C': 0.36927059691812875,
 'D': 0.24112322652876766,
 'E': 0.15948973783805293}

Assignment¶

In [29]:
# 1)
# design a function that can compute HITS Algorithm by using the following graph
In [30]:
# generate random graph
G = nx.fast_gnp_random_graph(50, 0.2)
# weights
weights = []
# add random edge weights
for (u, v) in G.edges():
    w = random.randint(0,10)
    G.edges[u,v]['weight'] = w
    weights.append(w)
In [31]:
plt.figure(figsize=[12,8], dpi=300)
# positions
pos = nx.spring_layout(G, seed=2)  # positions for all nodes - seed for reproducibility
# nodes
nx.draw_networkx_nodes(G, pos, node_size=60, node_color='navy')
# edges
nx.draw_networkx_edges(G, pos, width=np.array(weights)/2, alpha=0.5, edge_color="gray", style="dashed")
# plot configurations
ax = plt.gca()
# ax.margins(0.1)
plt.axis("off")
plt.tight_layout()
plt.show()
In [32]:
# 2) run at least three centrality indicators and discuss their differences in your results
In [ ]: